The present disclosure generally relates to parallel computing, and particularly to methods of relaxing synchronization of data access during parallel computing, and systems for implementing the same, and machine readable storage media encoding a program for implementing the same.
Emerging applications in computing, particularly in the area of data analytics, predominantly use iterative convergence techniques to arrive at the desired solution. Typically, the computation consists of a set of iterations, each of which can be spawned as an individual thread which computes largely using data private to that thread, and globally synchronizing to contribute to the overall solution at a later step. In such scenarios, the application scales with the number of processors employed in parallel computing by utilizing multi-threaded concurrent execution of the iterations. However, one of the scalability challenges is the synchronization overhead which, in the worst case, can be the dominant portion of the program execution time.
One method for addressing the scalability problem in parallel computing is the privatization method. In the privatization method, multiple copies of the data are made so that each of the executing threads performs all the updates in the local copy. When all the iterations are complete, the master thread coordinates to merge all the updates from the other threads, and determines the convergence criteria for the overall solution. As the size of the data increases, it becomes difficult to scale to a large number of threads using this approach because the copying results in data bloat, and puts a strain on the memory bandwidth.
Another method for addressing the scalability problem in parallel computing is the lock-free synchronization method. The lock-free synchronization method employs atomic instructions (such as compare-and-swap) so that the overhead of synchronization is reducible. However, the method is limited to atomic operations on word-size data objects. For updating larger quantities of data, this method cannot be used directly, and hence the significant synchronization overhead remains.
Yet another method for addressing the scalability problem in parallel computing is the transaction-based synchronization method. In the transaction-based synchronization method, transactions can be considered as coarse-grain synchronization, and they offer reduction in synchronization overhead using speculation. However, not all application domains are amenable to this synchronization method. Furthermore, it is possible that the speculation, if incorrect, could lead to expensive rollback and recovery. Thus, the transaction-based synchronization method, if employed by itself, provides only a limited solution to the scalability problem.